To handle collision events between moving objects with each object moving relative to another, the relative movement of one object viewed from another object can be taken into account, reduced to a collision event between a stationary object and a moving object. Hereinafter, the discussions below will be focused on a collision event between a stationary object and a moving object.
As one technique for detecting a collision between such objects; there is a method for creating a sweep shape by sweeping the shape of a moving object along its trajectory and then determining whether or not the sweep shape and the shape of a stationary object are intersecting (hereinafter referred to as the sweep method). Also there is another method for determining whether or not the shapes of a moving object and a stationary object are intersecting, at every instant as defined by dividing the duration of movement from start to end by an appropriate interval (hereinafter referred to as the time division method). The fundamental difference between both methods lies in that a temporally continuous event of object movement is treated as it is or as a discrete one.
However, the sweep method has no efficient general-purpose technique of creating a sweep shape by an arbitrary movement of an arbitrary shape and, particularly, creating a sweep shape for a typical rigid body movement that accompanies not only a change in position but also a change in attitude. That is, the sweep method is not readily applicable but only to a specific case in which the moving object has a limited type of shape or movement. Furthermore, the sweep method has not been in practical use because it requires higher computational costs for determining whether a complicated sweep shape and a stationary object shape are intersecting.
The time division method is generally said to require lower computational costs as compared to the sweep method. However, finer division intervals increase the number of times of determining intersections, causing the overall computational costs not to be negligible. On the other hand, coarser division intervals cause a malfunction of the method, leading to a higher possibility of a collision being accidentally not detected.
In this context, based on the time division method, efforts have been made to cut computational costs per one determination of intersection. Such methods includes, for example, one disclosed in Patent Literature 1.